package com.github.yangyishe.p100;

import java.util.Arrays;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
 *
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 *
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * 示例 2：
 *
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 * 示例 3：
 *
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 *
 *
 * 提示：
 *
 * 0 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * nums 是一个非递减数组
 * -109 <= target <= 109
 */
public class Problem34 {
    public static void main(String[] args) {
        int[] nums=new int[]{5,7,7,8,8,10};
        int target=6;

        Problem34 problem34 = new Problem34();
        int[] ints = problem34.searchRange(nums, target);
        System.out.println(Arrays.toString(ints));

    }

    /**
     * 思路:
     * 按照灵茶山艾府老师的二分查找思路, 二分查找, 最重要的是分清开闭区间.
     * 首先, 将问题简化为: 找到 gte target的数字的最小索引.
     * 假定使用的左右指针, 都是闭区间. 则left的左侧开区间都是lt target的数字, right右侧开区间都是 gte target的数字
     * 之后使用二分查找, 每次都需要保证以上原则.
     * 找到最小索引left后, 在最小索引的基础上继续找gte target+1的最小索引, 最后得到的left2-1就是满足要求的最大索引范围
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        if(nums.length==0){
            return new int[]{-1,-1};
        }

        int lowBoundary=lowBoundary(nums,target,0,nums.length-1);
        if(lowBoundary==nums.length){
            return new int[]{-1,-1};
        }
        int highBoundary=lowBoundary(nums,target+1,lowBoundary,nums.length-1);
        if(lowBoundary==highBoundary){
            return new int[]{-1,-1};
        }

        return new int[]{lowBoundary,highBoundary-1};
    }

    private int lowBoundary(int[] nums,int target,int left,int right){
        int mid;
        // 因为是闭区间,可以使用lte
        while(left<=right){
            mid=(left+right)/2;
            if(nums[mid]<target){
                // 保证left的左侧开区间都是lt target的数字
                left=mid+1;
            }else{
                // 保证right右侧开区间,都是gte
                right=mid-1;
            }
        }
        return left;
    }
}
